package com.jinan.algorithm.Combinatorics;

import java.util.ArrayList;
import java.util.List;

public class PrimeNum {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
        System.out.println(linearSieveOfEratosthenes(100));
    }

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

    /**
     * 线性筛
     *
     * @param n
     * @return
     */
    public static int linearSieveOfEratosthenes(int n) {
        int[] spf = new int[n + 1]; // smallest prime factor array
        List<Integer> primes = new ArrayList<>();
//        boolean[] isPrime = new boolean[n + 1];

//        初始化一个数组spf（Smallest Prime Factor，最小质因数），用于存储每个数的最小质因数。
//        对于所有数i，初始时spf[i] = i，表示假设每个数都是素数。
        // Initialize SPF for every number to itself.
        for (int i = 2; i <= n; i++) {
            spf[i] = i;
        }

//遍历从2到n的每一个数i：
//如果spf[i]仍然等于i，说明i没有被之前的任何数筛除过，因此i是一个素数。
        // Mark SPF for every number to be the smallest prime number.
        for (int i = 2; i <= n; i++) {
            if (spf[i] == i) {
                primes.add(i);
            }
//            将i加入素数列表中，并用i去筛除所有形如i*j的合数，其中j是之前已经确定的素数，且满足i*j <= n。
//            这里有一个关键点：当i是j的倍数时，跳过此次筛除，因为i*j已经被更小的质因数筛除了。
//            更新spf[i*j]为j，表示i*j的最小质因数是j。
            for (Integer prime : primes) {
                if (i * prime > n) {
                    break;
                }
                spf[i * prime] = prime;
                if (i % prime == 0) {
                    break;
                }
            }
        }
        return primes.toArray().length;
    }
}
